1. Field of the Invention
The present invention relates to an error-correcting method and a decoder using the same.
2. Description of Related Art
FIG. 1 is a hardware block diagram of a prior art decoder. In the diagram, the reference numeral 1 designates a memory, 2 an address/data/control signal bus, 3 a Reed-Solomon decoder for a Reed-Solomon code, and 4 a control circuit. Description is given below by taking an (N, K, D) Reed-Solomon code on a Galois field GF(2.sup.8) as an example, where N denotes the code length, K denotes the number of information symbols, and D (D=N-K+1) denotes the minimum distance of the code. In this example, each symbol consists of 8 bits.
The generator polynomial for the Reed-Solomon code is; EQU G(x)=(X-.alpha..sup.i)(X-.alpha..sup.i+1) . . . (X-.alpha..sup.i+D-2)
where .alpha. is a primitive element in the Galois field GF(2), and i is an arbitrary integer, usually 0 or 1. Received word data D.sub.0, D.sub.1, . . . , D.sub.N-1 recovered from the transmitted codewords are stored at addresses #A.sub.0, #A.sub.1, . . . , #A.sub.N-1 in the memory 1 respectively. According to instructions from the control circuit 4, data D.sub.0, D.sub.1, . . . , D.sub.N-1 are transferred via the address/data/control signal bus 2 to the Reed-Solomon decoder 3, which corrects up to t.ltoreq.[(D-1)/2] errors caused during transmission through a transmission channel. Here, [x] is a Gaussian symbol denoting the largest integer under x. Detailed descriptions of control signals, timing, etc. are omitted here.
At a recent research meeting of Japan's Electronic Information Communications Society, a paper entitled "A Study on Binary Expanded Reed-Solomon codes" (IT91-42, hereinafter referred to as the prior art paper) was presented by Toshiyuki Konosu, Toshimitsu Kaneko, Toshinao Nishijima, Shigeichi Hirasawa, and others, in which they introduced a technique of expanding Reed-Solomon codes to binary BCH codes to increase the burst error correcting capability of the Reed-Solomon codes. The outline of the technique will now be described below.
Parameters are defined as follows
N: Code length of a Reed-Solomon code (N.ltoreq.2.sup.m -1) PA1 K: Number of information symbols in the Reed-Solomon code PA1 D: Minimum distance (D=N-K+1) of the Reed-Solomon code on GF(2.sup.m) PA1 .alpha.: Primitive element on GF(2.sup.m) PA1 m.sub.S (x): Irreducible polynomial of .alpha..sup.S on GF(2) PA1 G(x): Generator polynomial of the Reed-Solomon code PA1 (0 0 0 0 0 0 0 0 0 0 0 0 0 0 0) PA1 S.sub.1.i =.alpha..sup.i+9 PA1 S.sub.3.i =.alpha..sup.3i PA1 S.sub.1.i =.alpha..sup.i+6 PA1 S.sub.3.i =0
With these, the following sets are defined. EQU Z.sub.n ={0, 1, . . . , N-1} EQU R.sub.t ={i.vertline.m.sub.0 .ltoreq.i.ltoreq.m.sub.0 +N-K-1;i.epsilon.Zn} EQU C.sub.s ={i.vertline.i=2.sup.p S.epsilon.R.sub.t. 0.ltoreq.p.ltoreq.m-1}
Cs is a cycle set on GF(2) for .alpha..sup.S.Cs* is expressed by the following equation. EQU C.sub.S *={i.vertline..epsilon.({C.sub.s }.andgate.Z.sub.n)}
Using the generator polynomial m.sub.S (x) of the (N, K, N-K+1) Reed-Solomon code on GF(2.sup.m), G(x) can be expressed by the following equation. ##EQU1## In this case, a codeword C(x) for the Reed-Solomon code is expressed as; ##EQU2## Here, if the following equation (B) in the above equation (A) is regarded as a binary code of length N, it represents the BCH code generated by the following equation (C). ##EQU3##
The prior art paper discloses a decoding method whereby solid burst errors of burst length of m(t-1)+1.ltoreq.b.ltoreq.mt are corrected using a t-error correcting Reed-Solomon code on GF(2.sup.m). FIG. 2 is a flowchart illustrating the prior art method of increasing the burst error correction capability of the Reed-Solomon code by translating Reed-Solomon code into binary BCH codewords when decoding. First, in step S1, Reed-Solomon decoding on GF(2.sup.m) is performed to determine whether or not the number of errors is t or less. If the number of errors is t or less, error correction is performed and the positions and values of the errors are obtained. The process then proceeds to step S2. If it is decided that the number of errors is t+1 or greater, the process proceeds to step S3. In step S2, the errors are corrected in accordance with a known decoding method. On the other hand, in step S3, the irreducible polynomial m(x) is binary expanded. Next, in step S4, syndrome computation is performed on the m BCH codewords, and in step S5, the computed syndrome values are compared with predetermined syndrome patterns. If there is a syndrome matching the syndrome pattern, a table lookup is performed, using a ROM or the like, to find the error pattern corresponding to the syndrome for correction of the error in step S6. If there is no syndrome matching the syndrome pattern, error correction is not performed, but an error detection flag is set up in step S7.
In the prior art paper, the above operation is shown numerically. First, consider a (15, 2, 14) Reed-Solomon code for which generator polynomial on GF(2.sup.4) is ##EQU4## where .alpha. is a primitive element in GF(2.sup.4). Let the transmitted word be
Using the irreducible polynomial on GF(2.sup.4) EQU m.sub.1 (x)=X.sup.4 +X+1
the transmitted word is binary expanded to yield four BCH codewords of 15 in length for which generator polynomial is ##EQU5## This represents a (15, 2, 5) BCH code, which is a subcode of a (15, 7, 5) BCH code. .alpha., .alpha..sup.2, .alpha..sup.4, .alpha..sup.8, .alpha..sup.3, .alpha..sup.6, .alpha..sup.12, and .alpha..sup.9 are the roots. When a received word on GF(2.sup.4) is EQU (0 0 0 0 1 .alpha..sup.12 .alpha..sup.12 .alpha..sup.12 .alpha..sup.12 .alpha..sup.6 .alpha.0 0 0 0)
this means the presence of a solid burst of length of b=23(m(t-1)+1&lt;b.ltoreq.mt). Division for each basis gives EQU .alpha..sup.3 :(0 0 0 0 0 1 1 1 1 1 1 0 0 0 0) EQU .alpha..sup.2 :(0 0 0 0 0 1 1 1 1 1 1 0 0 0 0) EQU .alpha.:(0 0 0 0 0 1 1 1 1 1 0 0 0 0 0) (D) EQU 1:(000011111100000)
Thus, g.sup.b (x) has .alpha. and .alpha..sup.3 as independent roots. When the burst length b'=6 or 5, the syndrome is given by
(1) For b'=6 PA0 (2) For b'=5
Here, i denotes the burst start bit position counted from the last bit position as O bit in the received binary sequence. From equation (D), the followings are obtained; ##EQU6## Thus, error correction can be accomplished.
In "A Study on Reed-Solomon Code Decoding Utilizing Bit Minimum Distance" by Katsumi Sakakibara, Kinichiro Tokiwa, and Masao Kasahara (Japan's Electronic Information Communications Society, Technical Research Report IT86-28), another prior art is disclosed as a decoding technique whereby an (n, 2, n-1) Reed-Solomon code is decoded as an (mn, 2 m, (n-1) 2.sup.m) binary linear code. However, this technique is not really practical as it allows only 2 m information symbol bits and the encoding efficiency is as low as 2/n. Another paper "Decoding of Reed-Solomon Codes Based on Decoding Distance Profiles" by Katsumi Sakakibara, Kinichiro Tokiwa, Masao Kasahara, and Toshihiko Namekawa (1986 National Conference of Japan's Electronic Communications Society, 1407, pp.6-49), disclosed a method whereby a Reed-Solomon code of minimum distance of 4 is binary expanded and decoded as a SEC-DED code. Application of this method, however, is limited to Reed-Solomon codes of minimum distance of 4, and furthermore, this method requires classifying error patterns and solving many congruence equations.
FIG. 3 is a diagram showing eight random errors occurring in a Reed-Solomon code on GF(2.sup.4). Reference numeral 5 designates the error bits. In this case, the eight random errors cause eight symbol errors, the correction of which would require for the Reed-Solomon code to have the minimum distance of D=2t+1=17. Since this would require 16 redundant symbols, exceeding the codeword length of 15, construction of such a code would not be possible.